/*-------- Includes --------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/*-------- Defines --------*/
#define MAX_STRING_SIZE 1024
#define MAX_STACK_SIZE  128

/*-------- Types --------*/
enum TYPE {
    NUMBER, OPERATOR
};

class Node {
public:
    TYPE   type;
    double num;
    char   opt;
public:
    Node() {}

    Node(TYPE t, double d, char c) {
        type = t;
        num  = d;
        opt  = c;
    }
};

template <class T> class Stack {
private:
    T   *pdata;
    int cap;
    int top;
    int bot;

public:
    Stack(int c) {
        pdata = new T[c];
        cap   = c;
        top   = 0;
        bot   = 0;
    }

    ~Stack()         { delete [] pdata; pdata = NULL; }

    bool isEmpty()   { return top == bot; }

    int size()       { return top - bot; }

    void push(T t)   { if (top < cap) pdata[top++] = t; }

    T pop()          { return pdata[--top]; }

    void push_r(T t) { if (bot > 0) pdata[--bot] = t; }

    T pop_r()        { return pdata[bot++]; }
};

/*-------- Function prototypes --------*/
void trim(char **pp);
bool check(char *Expr);
bool isNum(char c);
bool isOpt(char c);
bool isBkt(char c);
void inToPost(char *expr, Stack<Node> *pfix);
int getRank(char c);
double calc(Stack<Node> *pfix);
double calc(char opt, double lhs, double rhs);

/*-------- Main function --------*/
int main(int argc, const char *argv[])
{
    char        temp;
    char        *expr = new char[MAX_STRING_SIZE];
    Stack<Node> *pfix = new Stack<Node>(MAX_STACK_SIZE);

    while (1) {
        int i;
        printf("Please enter your expression:\n");
        for (i = 0; (temp = getchar()) != '\n'; i++)
            expr[i] = temp;
        expr[i] = '\0';

        // 1. trim whitesapce
        trim(&expr);

        // 2. check expression
        if (!check(expr)) {
            printf("Invalid expression!\n\n");
            continue;
        }

        // 3. transform infix expression into postfix epression
        inToPost(expr, pfix);

        // 4. calculate
        printf("= %.4f\n\n", calc(pfix));
    }

    delete expr;
    delete pfix;
}

/*-------- Functions --------*/
void trim(char **pp)
{
    char *src = *pp;
    char *dst = new char[MAX_STRING_SIZE];

    int i;
    for (i = 0; *src != '\0'; src++) {
        if (*src == ' ') continue;

        dst[i++] = *src;
    }
    dst[i] = '\0';

    delete *pp;
    *pp = dst;
}

bool check(char *expr)
{
    char *p;
    int  count;

    // 1. check the first character
    if (isOpt(*expr)) return false;

    // 2. check whether all characters is valid
    for (p = expr; *p != '\0'; p++)
        if (!(isNum(*p) || isOpt(*p) || isBkt(*p)))
            return false;

    // 3. check whether operators are used properly
    for (p = expr; *p != '\0'; p++) {
        if (isOpt(*p)) {
            if (isOpt(p[-1]) || p[-1] == '(') return false;
            if (isOpt(p[1])  || p[1]  == ')') return false;
        }
    }

    // 4. check whether brackets are used properly
    for (p = expr; *p != '\0'; p++) {
        if      (*p == '(') count++;
        else if (*p == ')') count--;

        if (count < 0) return false;
    }

    return count == 0;
}

bool isNum(char c)
{
    return (c > 47 && c < 58) || c == '.';
}

bool isOpt(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

bool isBkt(char c)
{
    return c == '(' || c == ')';
}

void inToPost(char *expr, Stack<Node> *pfix)
{
    char        *p, *q;
    char        temp;
    Stack<char> opts(MAX_STACK_SIZE);

    for (p = expr; *p != '\0'; p++) {
        if (isNum(*p)) {            // read a number
            q = p;
            while (isNum(*++p));
            temp = *p; // save next token
            *p = '\0';
            Node node(NUMBER, atof(q), '\0');
            pfix->push(node);
            *p-- = temp; // revert
        } else if (isOpt(*p)) {     // read a operator
            while (!opts.isEmpty()) {
                // caution: temp = '('
                temp = opts.pop();
                if (getRank(*p) > getRank(temp)) {
                    opts.push(temp);
                    break;
                } else {
                    Node node(OPERATOR, 0.0, temp);
                    pfix->push(node);
                }
            }
            opts.push(*p);
        } else {                    // read parentheses
            if (*p == '(') {
                opts.push(*p);
            } else {
                while (!opts.isEmpty() && (temp = opts.pop()) != '(') {
                    Node node(OPERATOR, 0.0, temp);
                    pfix->push(node);
                }
            }
        }
    }

    while (!opts.isEmpty()) {
        Node node(OPERATOR, 0.0, opts.pop());
        pfix->push(node);
    }
}

int getRank(char c)
{
    if      (c == '^')             return 2;
    else if (c == '*' || c == '/') return 1;
    else if (c == '+' || c == '-') return 0;
    else                           return -1;
}

double calc(Stack<Node> *pfix)
{
    double        lhs, rhs;
    Node          temp;
    Stack<double> nStack(MAX_STACK_SIZE);

    while (!pfix->isEmpty()) {
        temp = pfix->pop_r();
        if (temp.type == NUMBER) {
            nStack.push(temp.num);
        } else {
            rhs = nStack.pop();
            lhs = nStack.pop();

            // printf("%.4f %c %.4f\n", lhs, temp.opt, rhs);
            nStack.push(calc(temp.opt, lhs, rhs));
        }
    }

    return nStack.pop();
}

double calc(char opt, double lhs, double rhs)
{
    double ret;

    switch (opt) {
        case '+': ret = lhs + rhs; break;
        case '-': ret = lhs - rhs; break;
        case '*': ret = lhs * rhs; break;
        case '/': ret = lhs / rhs; break;
        case '^': ret = pow(lhs, rhs); break;
        default : break;
    }

    return ret;
}
